package mht.leetCode.primary.linkedList;

import mht.practice.ListNode.ListNode;

public class Solution {


    /**
     * 【删除链表中的节点】
     * <p>
     * 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
     * <p>
     * 示例 1:
     * <p>
     * 输入: head = [4,5,1,9], node = 5
     * 输出: [4,1,9]
     * 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
     * <p>
     * 示例 2:
     * <p>
     * 输入: head = [4,5,1,9], node = 1
     * 输出: [4,5,9]
     * 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
     */
    public void deleteNode(ListNode node) {

        // 思路：主要明确该node是要删除的node
        if (node == null) {
            return;
        }

        node.val = node.next.val;
        node.next = node.next.next;
    }

    /**
     * 【删除链表的倒数第N个节点】
     *
     * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
     *
     * 示例：
     *
     * 给定一个链表: 1->2->3->4->5, 和 n = 2.
     *
     * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
     * 说明：
     *
     * 给定的 n 保证是有效的。
     *
     * 进阶：
     * 你能尝试使用一趟扫描实现吗？
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {

        if (head == null) {
            return head;
        }

        ListNode p = head;
        ListNode q = head;

        while (n>0 && p!=null) {
            p = p.next;
            n--;
        }

        if (p == null) {
            return head.next;
        }

        while (p.next != null) {
            p = p.next;
            q = q.next;
        }

        q.next = q.next.next;

        return head;
    }

    /**
     * 【回文链表】
     *
     * 请判断一个链表是否为回文链表。
     *
     * 示例 1:
     *
     * 输入: 1->2
     * 输出: false
     * 示例 2:
     *
     * 输入: 1->2->2->1
     * 输出: true
     *
     * 进阶：
     * 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
     */
    public boolean isPalindrome(ListNode head) {

        if (head == null || head.next == null) {
            return true;
        }


        // 思路：快慢指针，找到中间节点，翻转后半部分链表，之后与表头相比较，有不相等的就不是回文链表
        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        slow = slow.next;
        // 翻转后半部分链表
        ListNode p = null;

        while (slow != null) {
            ListNode preCur = slow;
            slow = slow.next;
            preCur.next = p;
            p = preCur;
        }

        while (p != null) {
            if (head.val != p.val) {
                return false;
            }
            head = head.next;
            p = p.next;
        }
        return true;
    }


    public static void main(String[] args) {

        Solution solution = new Solution();
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2);

        boolean res = solution.isPalindrome(node1);
        System.out.println(res);
    }

}
